Tìm đường đi ngắn nhất từ đỉnh B tới đỉnh D của đồ thị G[3]

- Bước 0: Ta đánh dấu đỉnh xuất phát = 0, các đinh còn lại bằng vô cực.

- Bước 1:

Tại đỉnh A có đỉnh B đi vào có chi phí hiện tại (2) < chi phí trước (∞) => cập nhật lại chi phí đỉnh A

Tại đỉnh C có đỉnh B đi vào có chi phí hiện tại (6) < chi phí trước (∞) => cập nhật lại chi phí đỉnh C

- Bước 2:

Tại đỉnh C có đỉnh A đi vào có chi phí hiện tại (5) < chi phí trước (6) => cập nhật lại chi phí đỉnh C

Tại đỉnh D có đỉnh C đi vào có chi phí hiện tại (8) < chi phí trước (∞) => cập nhật lại chi phí đỉnh D

- Bước 3:

Tại đỉnh D có đỉnh A đi vào có chi phí hiện tại (7) < chi phí trước (8) => cập nhật lại chi phí đỉnh D

- Bước 4:

Bước 4 giống bước 3 nên thuật toán dừng.

- Kết luận:

Có đường đi ngắn nhất từ B->D: B->A->C->D

- Lưu ý:

Nếu bước 4 không giống bước 3 => kết luận không có đường đi ngắn nhất từ B->D